Problem statement: zenit12ckh

Jednou z intenzívne diskutovaných otázok je ochrana proti škodcom. V poslednej dobe musia farmy čeliť početným expanziám pásavky zemiakovej (známej aj pod menom Trumanov chrobák) a tiež vošiek. Účinná ochrana proti týmto dvom živočíšnym pohromám je dnes základ úspešného hospodárstva. Farmárska oblasť na južnom Slovensku sa rozhodla spolupracovať pri vytvorení systému ochrany.

Oblasť tvorí niekoľko fariem. Medzi niektorými dvojicami panuje bilaterálna dohoda o spolupráci. Každá farma si môže kúpiť účinnú ochranu proti obom uvedeným nástrahám. Keďže je to ale príliš nákladné, spoločenstvo sa rozhodlo, že každý bude mať ochranu len proti jednej z týchto hrozieb.

Škodcovia farmu nenapadajú zo sekundy na sekundu, ale postupne. Ak farma nemá možnosť brániť sa proti hrozbe samostatne, stačí, ak má príslušný chemický prostriedok spolu s nástrojmi na jeho aplikáciu niektorá z bezprostredne spolupracujúcich fariem. Zistite, či je možné vytvoriť účinnú sieť ochrany za predpokladov, že každá farma si kúpi jednu ochranu a ak áno, nájdite jeden vyhovujúci rozpis.

Na prvom riadku vstupu sú dve celé čísla: počet fariem N a počet spolupracujúcich dvojíc M. Platí 1 ≤ N ≤ 100,000 a 0 ≤ M ≤ 500,000. Farmy si očíslujeme od 1 do N. Na každom z ďalších M riadkov je dvojica celých čísel x,y, ktorá hovorí, že farmy x a y spolupracujú. Čísla x a y sú samozrejme z rozsahu od 1 po N, sú rôzne a každá dvojica sa na vstupe vyskytne najviac raz.

Ak farmy nedokážu vybudovať systém ochrany, vypíšte NEDA SA. Ak nejaký existuje, vypíšte N riadkov. Každý riadok bude tvaru cislo: vosky alebo cislo: pasavka, hovoriaci, proti ktorému škodcovi sa má brániť farma s príslušným číslom. Farmy zoraďte podľa čísla vzostupne. Ak je možností viac, vypíšte ľubovoľnú.

5 5
1 3
3 2
3 4
5 2
5 4

    
  

1: vosky
2: vosky
3: pasavka
4: vosky
5: pasavka

    
  

5 4
1 3
2 4
4 5
5 2

    
  

1: vosky
2: vosky
3: pasavka
4: pasavka
5: vosky

    
  

6 7
1 2
3 4
4 6
3 6
2 3
1 6
1 3

    
  

NEDA SA